import java.util.Arrays;

public class BasicBinarySearch {
    public static boolean search(int[] nums,int target){
        if(nums == null || nums.length == 0){
            return false;
        }
        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int mid = (right+left)/2;
            if(nums[mid] == target){
                return true;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return false;
    }

    public int[] searchRange(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return new int[]{-1,-1};
        }
        int firstIndex = findFirstIndex(nums,target);
        if(firstIndex == -1){
            return new int[]{-1,-1};
        }
        int lastIndex = findLastIndex(nums,target);
        return new int[]{firstIndex,lastIndex};
    }

    private static int findFirstIndex(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;

        while(left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] == target){
                if(mid == 0 || nums[mid-1] < target){
                    return mid;
                } else{
                    right = mid -1;
                }
            } else if(nums[mid] > target){
                right = mid - 1;
            } else{
                left = mid + 1;
            }
        }
        return -1;
    }

    private static int findLastIndex(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;

        while(left <= right){
            int mid = left+(right-left)/2;
            if(nums[mid] == target){
                if( mid == nums.length-1 || nums[mid+1] > target ){
                    return mid;
                } else{
                    left = mid + 1;
                }
            }else if(nums[mid] > target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return -1;
    }

    public int peakIndexInMountainArray(int[] arr) {
        int left = 0 ;
        int right = arr.length-1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(arr[mid+1]<arr[mid] && arr[mid-1]<arr[mid]){
                return mid;
            }else{
                if(arr[mid] < arr[mid+1]){
                    left = mid+1;
                }else {
                    right = mid;
                }
            }
        }
        return -1;
    }

    public int findMin(int[] nums) {
        for(int i = 1; i < nums.length; i++){
            if(nums[i] < nums[i-1]){
                return nums[i];
            }
        }
        return nums[0];
    }

    public int search1(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return -1;
        }
        int left = 0;
        int right = nums.length-1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] == target){
                return mid;
            }
            // 左边有序
            if(nums[left] <= nums[mid]){
                // 目标刚好在有序的区间
                if(target >= nums[left] && target < nums[mid]){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else{
                // 右边有序
                if(target > nums[mid] && target <= nums[right]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,5,10,22,31};
        boolean result = search(nums, 1);
        System.out.println(result);
    }


}
